/**
 * @author 徐楠
 * @date 2022/1/12 22:03
 * @version 1.0
 */

package com.xunan.likou;

import java.util.Arrays;

public class TwoMissingNumbers {
    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        int[] result = missingTwo(nums);
        System.out.println(result);

    }


    public static int[] missingTwo(int[] nums) {
        // 首先明确一共需要多少个数字（范围）
        int n = nums.length + 2;
        // 对当前已有的序列求和
        int sum = Arrays.stream(nums).sum();
        // 根据等差数列求和方法，求出目标和与当前和的差值，差值即为两个缺失数字的和
        int diff = n * (n + 1) / 2 - sum;
        // 找到两个数字的分界线，一定是分界线两边各有一个，因为两个数字不会重复嘛
        int divide = diff / 2;
        // 接着求出其中一边应有的和为多少，还是等差数列求和方法
        sum = divide * (divide + 1) / 2;
        // 然后在分界线一边逐渐找到这个值
        for (int num : nums) {
            if (num <= divide) {
                sum -= num;
            }
        }
        // 相减得到另一个值
        return new int[]{sum, diff - sum};
    }

    /**
     * 使用位运算异或, 异或的规则 a^b=c c^b=a, 0x01^0x10=0x11 0x11^0x01=0x10
     * 所以可以先把1到N的异或结果看做c, 数组的异或结果看做a, 他们俩异或可以求出b, 也就是正好缺的2个数的异或结果。
     * 下一步就是如何找出其中一个数, 设这两个数为i和j, 因为b是他们的异或结果,
     * 所以b中二进制位为1的部分就是i和j不等的部分
     * 可以把最右边的第一个1的位置找出来, 假如b = 0x101 那么找到 0x001
     * 找到这个位置有什么用呢？因为这个1~N的数列是递增的，他里面的值可以根据这个位置大致平均的分为2批数
     * 比如[1,2,3,4,5,6] [0x1,0x10,0x11,0x100,0x101,0x110]
     * 因为递增关系, 每个数二进制中某一位和它前面的数一定不一样, 在这个例子中就是最右边的第一位也就是刚找到的位置
     * 那这样的话可以把1~N其中一批比如该位是1的这一批数做异或求出一个结果x，
     * 再把数组中同样这一批这一位是1的数做异或求出一个结果y，
     * 然后把x和y做一次异或就能得出缺失的这2个数中的其中一个了，剩下一个自然也就知道了。
     */
    public static int[] missingTwo2(int[] nums) {
        int sum = 0;
        for (int i = 1; i <= nums.length + 2; i++) {
            sum ^= i;
        }
        for (int i = 0; i < nums.length; i++) {
            sum ^= nums[i];
        }

        int diff = 0;
        for (int i = 1; i <= 32; i++) {
            if ((sum >> i & 1) == 1) {
                diff = i;
                break;
            }
        }
        int num1 = 0;
        for (int i = 1; i <= nums.length + 2; i++) {
            if ((i >> diff & 1) == 1) {
                num1 ^= i;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] >> diff & 1) == 1) {
                num1 ^= nums[i];
            }
        }
        return new int[]{num1, sum ^ num1};
    }


}
